{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Boomerangs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfBoomerangs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #回旋镖的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定平面上<em>&nbsp;</em><code>n</code><em> </em>对 <strong>互不相同</strong> 的点&nbsp;<code>points</code> ，其中 <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 。<strong>回旋镖</strong> 是由点&nbsp;<code>(i, j, k)</code> 表示的元组 ，其中&nbsp;<code>i</code>&nbsp;和&nbsp;<code>j</code>&nbsp;之间的距离和&nbsp;<code>i</code>&nbsp;和&nbsp;<code>k</code>&nbsp;之间的欧式距离相等（<strong>需要考虑元组的顺序</strong>）。</p>\n",
    "\n",
    "<p>返回平面上所有回旋镖的数量。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[0,0],[1,0],[2,0]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>两个回旋镖为 <strong>[[1,0],[0,0],[2,0]]</strong> 和 <strong>[[1,0],[2,0],[0,0]]</strong>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[1,1],[2,2],[3,3]]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[1,1]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n ==&nbsp;points.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 500</code></li>\n",
    "\t<li><code>points[i].length == 2</code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li>所有点都 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-boomerangs](https://leetcode.cn/problems/number-of-boomerangs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-boomerangs](https://leetcode.cn/problems/number-of-boomerangs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0],[1,0],[2,0]]', '[[1,1],[2,2],[3,3]]', '[[1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        ret = 0\n",
    "        for p1 in points:\n",
    "            hash = {}\n",
    "            for p2 in points:\n",
    "                if p2 == p1:\n",
    "                    continue\n",
    "                dis_squre = (p2[0]-p1[0]) ** 2 + (p2[1]-p1[1]) ** 2\n",
    "                if dis_squre not in hash:\n",
    "                    hash[dis_squre] = 1\n",
    "                else:\n",
    "                    hash[dis_squre] += 1\n",
    "\n",
    "            for key, value in hash.items():\n",
    "                if value >= 2:\n",
    "                    ret += value*(value-1)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math \n",
    "import copy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        l = len(points)\n",
    "\n",
    "        d = [[0]*l for i in range(l)]\n",
    "\n",
    "        for i in range(l):\n",
    "            cnt = defaultdict(int)\n",
    "            for j in range(l):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                \n",
    "                distance = math.sqrt((points[i][0]-points[j][0])**2 + (points[i][1]-points[j][1])**2)\n",
    "                cnt[distance] += 1\n",
    "            for v in cnt.values():\n",
    "                res += v * (v - 1)\n",
    "                \n",
    "\n",
    "        \n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def haha(self, a):\n",
    "        l = len(a)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        res = 0\n",
    "        while j < l:\n",
    "            if j == l - 1 or a[j + 1] != a[j]:\n",
    "                res += (j - i + 1) * (j - i)\n",
    "                i = j + 1\n",
    "            j += 1\n",
    "        return res\n",
    "\n",
    "    def numberOfBoomerangs(self, points):\n",
    "        l = len(points)\n",
    "        g = [[0 for i in range(l)] for j in range(l)]\n",
    "        for i in range(l):\n",
    "            for j in range(i + 1, l):\n",
    "                _ = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2\n",
    "                g[i][j] = _\n",
    "                g[j][i] = _\n",
    "        res = 0\n",
    "        for i in range(l):\n",
    "            res += self.haha(list(sorted(g[i])))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\r\n",
    "        from collections import Counter\r\n",
    "        arr = [[0 for __ in range(len(points))] for _ in range(len(points))]\r\n",
    "        for i in range(len(points)):\r\n",
    "            for j in range(i+1, len(points)):\r\n",
    "                arr[i][j] = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2\r\n",
    "                arr[j][i] = arr[i][j]\r\n",
    "        ret = 0\r\n",
    "        for i in range(len(arr)):\r\n",
    "            cnts = Counter(arr[i])\r\n",
    "            for _, value in cnts.items():\r\n",
    "                ret += value * (value - 1)\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        if len(points) < 3:\n",
    "            return 0\n",
    "        \n",
    "        count = 0\n",
    "        n = len(points)\n",
    "        distances = []\n",
    "        for _ in range(n):\n",
    "            distances.append([0] * n)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                p1 = points[i]\n",
    "                p2 = points[j]\n",
    "                dis = (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2\n",
    "                distances[i][j] = distances[j][i] = dis\n",
    "        \n",
    "        buf = {}\n",
    "        def comb2(v):\n",
    "            if v in buf:\n",
    "                return buf[v]\n",
    "            res = v*(v-1)\n",
    "            buf[v] = res\n",
    "            return res\n",
    "\n",
    "        from collections import Counter\n",
    "        def numEqualPair(distance):\n",
    "            n = 0\n",
    "            count = Counter(distance)\n",
    "            for v in count.values():\n",
    "                if v>0:\n",
    "                    n += comb2(v)\n",
    "            return n\n",
    "\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            n = numEqualPair(distances[i])\n",
    "            count += n\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        # from collections import defaultdict\n",
    "        l=len(points)\n",
    "        if l<3:\n",
    "            return 0\n",
    "        s=[[0]*i for i in range(1,l)]\n",
    "        for i in range(l-1):\n",
    "            for j in range(i+1):\n",
    "                # s[i][j]是points[i+1]与points[j]的距离的平方\n",
    "                s[i][j]=((points[i+1][0]-points[j][0])**2)+((points[i+1][1]-points[j][1])**2)\n",
    "        r=0\n",
    "        for i in range(l):\n",
    "            pd=defaultdict(int)\n",
    "            for j in range(i):\n",
    "                pd[s[i-1][j]]+=1\n",
    "            for j in range(i,l-1):\n",
    "                pd[s[j][i]]+=1\n",
    "            for j in pd.keys():\n",
    "                q=pd[j]\n",
    "                r+=q*(q-1)\n",
    "        return r\n",
    "\n",
    "\n",
    "\n",
    "        \"\"\"\n",
    "        p=[0]*(l-1)\n",
    "        for i in range(l):\n",
    "            for j in range(i):\n",
    "                p[j]=s[i-1][j]\n",
    "            for j in range(i,l-1):\n",
    "                p[j]=s[j][i]\n",
    "            p.sort()\n",
    "            j=0\n",
    "            while j<l-1:\n",
    "                a=p[j]\n",
    "                n=j\n",
    "                j+=1\n",
    "                while j<l-1 and p[j]==a:\n",
    "                    j+=1\n",
    "                n=j-n\n",
    "                r+=n*(n-1)\n",
    "        return r\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                dp[i][j]=(points[j][1]-points[i][1])**2 + (points[j][0]-points[i][0])**2\n",
    "                dp[j][i]=dp[i][j]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            res = Counter(dp[i])\n",
    "            temp = 0\n",
    "            for v in res.values():\n",
    "                if v>1:\n",
    "                    temp += v*(v-1)\n",
    "            ans += temp\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        def factorial(n):\n",
    "            if n==0:\n",
    "                return 1\n",
    "            else:\n",
    "                #递归调用\n",
    "                return factorial(n-1)*n\n",
    "        n = len(points)\n",
    "\n",
    "        # dp[i][j]表示points[i]与points[j]的距离\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                dp[i][j] = (points[i][0]-points[j][0])*(points[i][0]-points[j][0]) + \\\n",
    "                        (points[i][1]-points[j][1])*(points[i][1]-points[j][1])\n",
    "        result = 0\n",
    "        if n > 2:\n",
    "            for i in range(n):\n",
    "                data = []\n",
    "                for j in range(i):\n",
    "                    data.append(dp[j][i])\n",
    "                for k in range(i+1,n):\n",
    "                    data.append(dp[i][k])\n",
    "                set_data = set(data)\n",
    "                for i in list(set_data):\n",
    "                    q = data.count(i)\n",
    "                    if q > 1:\n",
    "                        result = result + factorial(q)//factorial(q-2)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        p = defaultdict(list)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                dis = (points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2\n",
    "                p[tuple(points[i])].append(dis)\n",
    "                p[tuple(points[j])].append(dis)\n",
    "        ans = 0\n",
    "        for lst in p.values():\n",
    "            c = Counter(lst)\n",
    "            for v in c.values():\n",
    "                ans += v*(v-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        dist=[[0 for _ in range(len(points))] for _ in range(len(points))]\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i,len(points)):\n",
    "                dist[i][j]=dist[j][i]=(points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2\n",
    "        ant=0\n",
    "        for i in range(len(points)):\n",
    "            m={}\n",
    "            for j in range(len(points)):\n",
    "                dis=dist[i][j]\n",
    "                if m.get(dis)==None:\n",
    "                    m[dis]=0\n",
    "                m[dis]+=1\n",
    "            for i in m:\n",
    "                if m[i]>=2:\n",
    "                    ant=ant+m[i]*(m[i]-1)\n",
    "        \n",
    "        return ant\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        res = [[] for _ in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                d2 = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2\n",
    "                res[i].append(d2)\n",
    "                res[j].append(d2)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            cnt = Counter(res[i])\n",
    "            for k, v in cnt.items():\n",
    "                ans += v * (v - 1)\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        final = 0\n",
    "        from collections import Counter\n",
    "        from collections import defaultdict\n",
    "        dis_dict = defaultdict(list)\n",
    "        def dis(pt1,pt2):\n",
    "            return ( (pt1[1]-pt2[1])**2 + (pt1[0]-pt2[0])**2 )\n",
    "\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(points)):\n",
    "                dis_dict[i].append(dis(points[i],points[j]))\n",
    "            dict_counter = Counter(dis_dict[i])\n",
    "            # print(dict_counter)\n",
    "            for key,value in dict_counter.items():\n",
    "                if value > 1:\n",
    "                    final += value*(value-1) \n",
    "        \n",
    "        # print(final)\n",
    "        return final\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oula(self, point1, point2):\n",
    "        dist = math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)\n",
    "        return dist\n",
    "\n",
    "    def numberOfBoomerangs(self, points):\n",
    "        n = len(points)\n",
    "        distlist = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                distlist[i][j] = self.oula(points[i], points[j])\n",
    "\n",
    "        for k in range(n):\n",
    "            for j in range(0, k):\n",
    "                distlist[k][j] = distlist[j][k]\n",
    "\n",
    "        countlist = []\n",
    "        for m in range(n):\n",
    "            temp = collections.Counter(distlist[m])\n",
    "            temp[0] -= 1\n",
    "            countlist.append(list(temp.values()))\n",
    "\n",
    "        count = 0\n",
    "        for q in range(n):\n",
    "            for i in countlist[q]:\n",
    "                if i >= 2:\n",
    "                    count += i * (i - 1)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n=len(points)\n",
    "        f=[[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                f[i][j]=(points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            c=defaultdict(int)\n",
    "            for j in range(n):\n",
    "                res+=c[f[i][j]]*2\n",
    "                c[f[i][j]]+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        length=len(points)\n",
    "        if length<3:return 0\n",
    "            \n",
    "        dic=defaultdict(list)\n",
    "        def d(p1,p2):\n",
    "            return (abs(p1[0]-p2[0])**2+abs(p1[1]-p2[1])**2)\n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                dic[str(i)].append(d(i,j))\n",
    "        ans=0\n",
    "        for arr in dic.values():\n",
    "            count=Counter(arr)\n",
    "            for v in count.values():\n",
    "                if v>1:\n",
    "                    ans+=v*(v-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points):\n",
    "        n = len(points)\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        distance = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j:\n",
    "                    distance[i][j] = (points[i][0] - points[j][0]) ** 2 + (\n",
    "                        points[i][1] - points[j][1]\n",
    "                    ) ** 2\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            distance[i].sort()\n",
    "            count = {}\n",
    "            for j in range(n):\n",
    "                if distance[i][j] not in count:\n",
    "                    count[distance[i][j]] = 1\n",
    "                else:\n",
    "                    count[distance[i][j]] += 1\n",
    "            for value in count.values():\n",
    "                if value >= 2:\n",
    "                    res += value * (value - 1)\n",
    "        return res\n",
    "\n",
    "\n",
    "Solution().numberOfBoomerangs([[1, 1], [2, 2], [3, 3]])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dis_matrix(self, points):\n",
    "        res = [[0 for i in range(len(points))] for j in range(len(points))]\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1, len(points)):\n",
    "                dis = (points[i][0]-points[j][0])*(points[i][0]-points[j][0])+(points[i][1]-points[j][1])*(points[i][1]-points[j][1])\n",
    "                res[i][j] = dis\n",
    "                res[j][i] = dis\n",
    "        return res\n",
    "\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        matrix = self.dis_matrix(points)\n",
    "        print(matrix)\n",
    "        for i in range(len(matrix)):\n",
    "            kv = {}\n",
    "            for j in range(len(matrix)):\n",
    "                if matrix[i][j] not in kv:\n",
    "                    kv[matrix[i][j]] = 1\n",
    "                else:\n",
    "                    res += kv[matrix[i][j]]\n",
    "                    kv[matrix[i][j]] += 1\n",
    "        return res+res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        dp = {(x[0],x[1]):{} for x in points}\n",
    "        n = len(points)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                p1 = (points[i][0],points[i][1])\n",
    "                p2 = (points[j][0],points[j][1])\n",
    "                dist = pow(p1[0]-p2[0], 2) + pow(p1[1]-p2[1], 2)\n",
    "\n",
    "                if dist not in dp[p1]:\n",
    "                    dp[p1][dist] = 0\n",
    "                dp[p1][dist] += 1\n",
    "                if dist not in dp[p2]:\n",
    "                    dp[p2][dist] = 0\n",
    "                dp[p2][dist] += 1\n",
    "        # print(dp)\n",
    "\n",
    "        res = 0\n",
    "        for dictPoint in dp.values():\n",
    "            for num in dictPoint.values():\n",
    "                if num >=2:\n",
    "                    res += num*(num-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n=len(points)\n",
    "        d=[Counter() for _ in range(n)]\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            x1,y1=points[i]\n",
    "            for j in range(i):\n",
    "                x2,y2=points[j]\n",
    "                dis=(x1-x2)**2+(y1-y2)**2\n",
    "                ans+=d[i][dis]*2\n",
    "                ans+=d[j][dis]*2\n",
    "                d[i][dis]+=1\n",
    "                d[j][dis]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "    l = len(points)\n",
    "    r = [{} for _ in range(l)]\n",
    "    ret = 0\n",
    "    for i in range(l):\n",
    "      x, y = points[i]\n",
    "      for j in range(i + 1, l):\n",
    "        x1, y1 = points[j]\n",
    "        d = (x1 - x) ** 2 + (y1 - y) ** 2\n",
    "        r[i][d] = r[i].get(d, 0) + 1\n",
    "        r[j][d] = r[j].get(d, 0) + 1\n",
    "      # print(f\"{i} r {r}\")\n",
    "      for k, v in r[i].items():\n",
    "        if v >= 2:\n",
    "          ret = ret + math.perm(v, 2)\n",
    "    return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        def distance(p1,p2):\n",
    "            return pow(p1[0]-p2[0],2)+pow(p1[1]-p2[1],2)\n",
    "\n",
    "        n = len(points)\n",
    "        matrics = []\n",
    "        for i in range(n):\n",
    "            matrics.append({})\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                d = distance(points[i],points[j])\n",
    "                dic = matrics[i]\n",
    "                if d in dic:\n",
    "                    dic[d] +=1\n",
    "                else:\n",
    "                    dic[d] = 1\n",
    "                dic = matrics[j]\n",
    "                if d in dic:\n",
    "                    dic[d] +=1\n",
    "                else:\n",
    "                    dic[d] = 1\n",
    "            for k in matrics[i].keys():\n",
    "                f = matrics[i][k]\n",
    "                if f>1:\n",
    "                    res = res + f*(f-1)/2\n",
    "            \n",
    "        return int(res*2)\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        dicts = [defaultdict(int) for _ in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                distance = sqrt((points[i][0]-points[j][0])**2 + (points[i][1]- points[j][1])**2)\n",
    "                dicts[i][distance]+=1\n",
    "                dicts[j][distance]+=1\n",
    "        ans = 0\n",
    "        for d in dicts:\n",
    "            for i in d:\n",
    "                ans += d[i]*(d[i] - 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        l = len(points)\n",
    "        if l<3:\n",
    "            return 0\n",
    "        p = points.copy()\n",
    "        s = []\n",
    "        k = 0\n",
    "        for point in p:\n",
    "            r = []\n",
    "            for point2 in p:\n",
    "                dis = (point[0]-point2[0])**2+(point[1]-point2[1])**2\n",
    "                r.append(dis)\n",
    "            s.append(r)\n",
    "        print(s)\n",
    "\n",
    "        for i in s:\n",
    "            m = 1\n",
    "            f  = sorted(i)\n",
    "            j = 0\n",
    "            flag = 0\n",
    "            while j<l-1:\n",
    "                if flag == 0 and f[j] == f[j+1]:\n",
    "                    flag =1\n",
    "                    m+=1\n",
    "                elif flag ==1 and f[j] == f[j+1]:\n",
    "                    m+=1\n",
    "                elif flag ==1 and f[j] != f[j+1]:\n",
    "                    k+= m*(m-1)\n",
    "                    #print(m,' ',k)\n",
    "                    m=1\n",
    "                    flag=0\n",
    "                j+=1\n",
    "            if m!=1:\n",
    "                k+= m*(m-1)\n",
    "\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        if len(points) < 3:\n",
    "            return 0\n",
    "        n = len(points)\n",
    "\n",
    "        def get_dis(i, j):\n",
    "            return (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2\n",
    "\n",
    "        ret = 0\n",
    "        dis_dict = [dict() for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                dis = get_dis(i, j)\n",
    "                if dis not in dis_dict[i]:\n",
    "                    dis_dict[i][dis] = 0\n",
    "                if dis not in dis_dict[j]:\n",
    "                    dis_dict[j][dis] = 0\n",
    "                dis_dict[i][dis] += 1\n",
    "                dis_dict[j][dis] += 1\n",
    "        return sum([dc * (dc - 1) for k in range(n) for dc in dis_dict[k].values()])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n=len(points)\n",
    "        d=defaultdict(dict)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j:\n",
    "                    dis=(points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2\n",
    "                    res+=d[i].get(dis,0)*2\n",
    "                    d[i][dis]=d[i].get(dis,0)+1\n",
    "        #print(d)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(points)):\n",
    "            record = collections.defaultdict(int)\n",
    "            for j in range(len(points)):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                distance = ((points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2) ** 0.5\n",
    "                record[distance] += 1\n",
    "                ans += (record[distance] - 1) * 2\n",
    "            \n",
    "\n",
    "        return int(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n=len(points)\n",
    "        l=[]\n",
    "        for i in range(n):\n",
    "            g={}\n",
    "            for j in range(n):\n",
    "                x=(points[j][0]-points[i][0])**2+(points[j][1]-points[i][1])**2\n",
    "                if x in g:\n",
    "                    g[x]+=1\n",
    "                else:g[x]=1\n",
    "            l.append(g)\n",
    "\n",
    "        s=0\n",
    "        for i in l:\n",
    "            for j in i.values():\n",
    "                if j>1:\n",
    "                    s=s+j*(j-1)\n",
    "        return s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        dist_matrix = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        count = 0\n",
    "        num = []\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                dist_matrix[i][j] = math.sqrt((points[i][0]-points[j][0])**2 + (points[i][1]-points[j][1])**2)\n",
    "            num.append(Counter(dist_matrix[i]))\n",
    "            \n",
    "            aList = list(num[i].values())\n",
    "            print(aList)\n",
    "            for j in range(len(aList)):\n",
    "                if aList[j] > 1:\n",
    "                    count += aList[j] * (aList[j] - 1)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        length=len(points)\n",
    "        if length<3:\n",
    "            return 0\n",
    "        \n",
    "        import numpy as np\n",
    "        t=np.zeros((length,length))\n",
    "\n",
    "        for i in range(length):#行\n",
    "            for j in range(i+1,length):#行\n",
    "                d2=(points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2\n",
    "                t[i,j]=d2\n",
    "                t[j,i]=d2\n",
    "\n",
    "        ans=0   \n",
    "        for i in range(length):\n",
    "            a = t[i].tolist()\n",
    "            a.sort(reverse=True)\n",
    "\n",
    "            idx=1\n",
    "            count=1\n",
    "            for idx in range(1,length):\n",
    "                if a[idx-1]==a[idx]:\n",
    "                    count+=1\n",
    "                else:\n",
    "                    ans+=count*(count-1)\n",
    "                    count=1\n",
    "                idx+=1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        ds = [[0 for j in range(len(points))] for i in range(len(points))]\n",
    "\n",
    "\n",
    "        infos = []\n",
    "        maps = {}\n",
    "\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(points)):\n",
    "                ds[i][j] = (points[i][0] - points[j][0]) ** 2 +  (points[i][1] - points[j][1]) ** 2\n",
    "                if i!=j:\n",
    "                    key = ds[i][j]\n",
    "                    if key in maps:\n",
    "                        maps[key] += 1\n",
    "                    else:\n",
    "                        maps[key] = 1\n",
    "            infos.append(maps)\n",
    "            maps = {}\n",
    "        ans = 0\n",
    "        for maps in infos:\n",
    "            for k in maps:\n",
    "                if maps[k]>1:\n",
    "                    ans += (maps[k] - 1) * maps[k]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        d = np.zeros((n,n))\n",
    "        for i, point1 in enumerate(points):\n",
    "            for j, point2 in enumerate(points):\n",
    "                # if i >= j:\n",
    "                #     continue\n",
    "                d[i][j] = np.linalg.norm(np.array(point1)-np.array(point2))\n",
    "        d = np.absolute(d)\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            c = Counter(d[i])\n",
    "            for k in c:\n",
    "                if k and c[k] != 1:\n",
    "                    s += (c[k] * (c[k]-1))\n",
    "        \n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from itertools import combinations\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        '''\n",
    "        免不了的组合，需要把两两的距离算出来\n",
    "        不能用组合，超时了\n",
    "        \n",
    "        应该用数学：统计某点A为中心点，并且边长为d的数目cnt，记为t[A][d]。那么这样的回旋镖数目=cnt！\n",
    "        '''\n",
    "        def dis(a,b):\n",
    "            return sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)\n",
    "        dt={tuple(a+b):dis(a,b) for a,b in combinations(points,2)}\n",
    "        # print(dt)\n",
    "        res=0\n",
    "        for A in points:\n",
    "            tt={}\n",
    "            for B in points:\n",
    "                if B==A:\n",
    "                    continue\n",
    "                d=max(dt.get(tuple(A+B),0),dt.get(tuple(B+A),0))\n",
    "                if d not in tt:\n",
    "                    tt[d]=1\n",
    "                else:\n",
    "                    tt[d]+=1\n",
    "            # print(tt)\n",
    "            res+=sum([cnt*(cnt-1) for cnt in tt.values()])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        def dis(x,y):\n",
    "            return (y[0]-x[0])**2+(y[1]-x[1])**2\n",
    "        n=len(points)\n",
    "        ij_dict={}\n",
    "        dis_dict={}\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                dis_dict[f'{i}_{j}']=dis(points[i],points[j])\n",
    "        cnt=0\n",
    "        for i,a in enumerate(points):\n",
    "            i_dis_dict={}\n",
    "            for j,b in enumerate(points):\n",
    "                if i==j:\n",
    "                    continue\n",
    "                if i<j:\n",
    "                    d=dis_dict[f\"{i}_{j}\"]\n",
    "                else:\n",
    "                    d=dis_dict[f'{j}_{i}']\n",
    "                i_dis_dict[d]=i_dis_dict.get(d,0)+1\n",
    "            for key in i_dis_dict:\n",
    "                tmp=i_dis_dict[key]\n",
    "\n",
    "                cnt+=tmp*(tmp-1)\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        ss = {}\n",
    "        dd = collections.defaultdict(int)\n",
    "        # ss 用于储存距离，避免第二次计算，如果计算了dis(a,b) ,当求dis(b,a) 直接查ss 就可以了。存一半.\n",
    "        ans = 0\n",
    "        p = points\n",
    "        for m in p:\n",
    "            for n in p:\n",
    "                if m == n: continue\n",
    "\n",
    "                z = (m[0], m[1], n[0], n[1])\n",
    "                y = (n[0], n[1], m[0], m[1])\n",
    "                # 现在求m到n 的距离，把n到m 的距离 放入字典ss\n",
    "                if z in ss:\n",
    "                    dis = ss[z]\n",
    "                else:\n",
    "                    dis = (n[0] - m[0]) ** 2 + (n[1] - m[1]) ** 2\n",
    "                    ss[y] = dis\n",
    "\n",
    "                dd[dis] += 1\n",
    "\n",
    "            for v in dd.values(): \n",
    "                ans += v **2 - v\n",
    "            dd.clear()  # 卸磨杀驴\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dis(i, j):\n",
    "            a, b = points[i], points[j]\n",
    "            return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(points)):\n",
    "            count = Counter()\n",
    "            for j in range(len(points)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                distance = dis(min(i, j), max(i, j))\n",
    "                count[distance] += 1\n",
    "            for value in count.values():\n",
    "                if value >= 2:\n",
    "                    res += value * (value - 1)\n",
    "        return int(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        if len(points) <=1: return 0\n",
    "        distance = collections.defaultdict()\n",
    "        n = len(points)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                distance[(i,j)] = (points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            cnt = collections.defaultdict(int)\n",
    "            for j in range(n):\n",
    "                if i == j: continue\n",
    "                dis = distance[(min(i,j),max(i, j))]\n",
    "                cnt[dis]+=1\n",
    "            for m in cnt.values():\n",
    "                ans+=m*(m-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dis(i, j):\n",
    "            xi, yi = points[i]\n",
    "            xj, yj = points[j]\n",
    "            return (xi-xj)*(xi-xj) + (yi-yj)*(yi-yj)\n",
    "        ret = 0\n",
    "        for i in range(len(points)):\n",
    "            d = defaultdict(int)\n",
    "            for j in range(len(points)):\n",
    "                if i > j:\n",
    "                    d[dis(j, i)] += 1\n",
    "                else:\n",
    "                    d[dis(i, j)] += 1\n",
    "            for v in d.values():\n",
    "                if v > 1:\n",
    "                    ret += v * (v-1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        dis = [[] for i in range(n)]\n",
    "\n",
    "        for i, p1 in enumerate(points):\n",
    "            for j in range(i + 1, n):\n",
    "                p2 = points[j]\n",
    "                d = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2\n",
    "                dis[i].append((d, j))\n",
    "                dis[j].append((d, i))\n",
    "\n",
    "\n",
    "        result = 0\n",
    "        for i, l in enumerate(dis):\n",
    "            l.sort(key=lambda x: x[0])\n",
    "            d = None\n",
    "            count = 0\n",
    "            for p in l:\n",
    "                if d is None or p[0] != d:\n",
    "                    if count >= 2:\n",
    "                        result += (count * (count - 1))\n",
    "                    d = p[0]\n",
    "                    count = 1\n",
    "                else:\n",
    "                    count += 1\n",
    "\n",
    "            if count >= 2:\n",
    "                result += (count * (count - 1))\n",
    "\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        p_len = len(points)\n",
    "        len_dic = {}\n",
    "        for i in range(p_len):\n",
    "            t_data = {}\n",
    "            t_dic ={}\n",
    "            for j in range(p_len):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if j in len_dic:\n",
    "                    t_len = len_dic[j][1][i]\n",
    "                else:\n",
    "                    t_len = self.get_len(i, j, points)\n",
    "                t_dic[j] = t_len\n",
    "                if t_len not in t_data:\n",
    "                    t_data[t_len] =0\n",
    "                t_data[t_len]+=1\n",
    "            len_dic[i] = [t_data, t_dic]\n",
    "\n",
    "        data = 0\n",
    "        for v in len_dic.values():\n",
    "            for t_v in v[0].values():\n",
    "                if t_v == 1:\n",
    "                    continue\n",
    "                data += self.get_count(t_v)\n",
    "        return data\n",
    "                \n",
    "    def get_count(self, n):\n",
    "        return n * (n - 1)\n",
    "                \n",
    "    def get_len(self, i, j, points):\n",
    "        return (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        matrix = [[0] * len(points) for _ in range(len(points))]\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(points)):\n",
    "                matrix[i][j] = (abs(points[i][0] - points[j][0])) * (abs(points[i][0] - points[j][0])) + (abs(points[i][1] - points[j][1])) * (abs(points[i][1] - points[j][1]))\n",
    "        res = 0\n",
    "        point2times = dict()\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(points)):\n",
    "                point2times[i] = point2times.get(i, {}) \n",
    "                point2times[i][(abs(points[i][0] - points[j][0])) * (abs(points[i][0] - points[j][0])) + (abs(points[i][1] - points[j][1])) * (abs(points[i][1] - points[j][1]))] = point2times[i].get((abs(points[i][0] - points[j][0])) * (abs(points[i][0] - points[j][0])) + (abs(points[i][1] - points[j][1])) * (abs(points[i][1] - points[j][1])), 0) + 1\n",
    "        for i in range(len(points)):\n",
    "            for key, val in point2times[i].items():\n",
    "                if val >= 2:\n",
    "                    res += val * (val - 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.special import comb\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        if len(points)<3:\n",
    "            return 0\n",
    "\n",
    "        ans = 0\n",
    "        for p in points:\n",
    "            cnt = defaultdict(int)\n",
    "            for q in points:\n",
    "                dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])\n",
    "                cnt[dis] += 1\n",
    "            for m in cnt.values():\n",
    "                ans += m * (m - 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.special import perm\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        n = len(points)\n",
    "        for i in range(n):\n",
    "            hashmap = {}\n",
    "            for j in range(n):\n",
    "                if i==j: \n",
    "                    continue\n",
    "                num = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2\n",
    "                 \n",
    "                if num in hashmap: \n",
    "                    hashmap[num] = hashmap[num] + 1\n",
    "                else:\n",
    "                    hashmap[num] = 1\n",
    "\n",
    "            for key in hashmap:\n",
    "                res += hashmap[key] * (hashmap[key] - 1)\n",
    "        return res\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        from scipy.special import perm\n",
    "        def two(nums):\n",
    "            dic=collections.Counter(nums)\n",
    "            return sum([perm(dic[x],2) for x in dic if dic[x]>=2])\n",
    "        def distance(x,y):\n",
    "            return (x[0]-y[0])**2+(x[1]-y[1])**2\n",
    "        ans=0\n",
    "        for i in range(len(points)):\n",
    "            ans+=two([distance(points[i],points[j]) for j in range(len(points))])\n",
    "        return int(ans)\n",
    "        \n",
    "        \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        dic = {}\n",
    "        N = len(points)\n",
    "        res = 0\n",
    "\n",
    "        def cal_dis(x,y):\n",
    "            return (x[0]-y[0])**2 + (x[1]-y[1])**2\n",
    "\n",
    "        def cal_num(n):\n",
    "            return n*(n-1)\n",
    "\n",
    "        for x_index,x in enumerate(points):\n",
    "            if x_index not in dic:\n",
    "                dic.setdefault(x_index,[])\n",
    "            for y_index in range(x_index+1,N):\n",
    "                dic[x_index].append((y_index,cal_dis(x,points[y_index])))\n",
    "                if y_index not in dic:\n",
    "                    dic.setdefault(y_index,[])\n",
    "                dic[y_index].append((x_index,cal_dis(x,points[y_index])))\n",
    "            dic[x_index].sort(key = lambda x:x[1])\n",
    "        \n",
    "        for i in range(N):\n",
    "            j = 0\n",
    "            k = 1\n",
    "            while j < N-1:\n",
    "                while k < N-1 and dic[i][j][1] == dic[i][k][1]:\n",
    "                    k += 1\n",
    "                res += cal_num(k-j)\n",
    "                j = k\n",
    "        return res\n",
    "                \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "from scipy.special import comb, perm\n",
    "\n",
    "class Solution:\n",
    "    def get_dist(self, point01:List[int],point02:List[int]) -> float:\n",
    "        return np.square(point01[0]-point02[0])+np.square(point01[1]-point02[1])\n",
    "\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        dist=np.zeros((n,n))\n",
    "        total = int(0)\n",
    "        \n",
    "        if n<3 :\n",
    "            return 0\n",
    "        \n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i==j :\n",
    "                    dist[i,j]=0\n",
    "                else:\n",
    "                    dist[i,j]=Solution.get_dist(self,points[i],points[j])\n",
    "\n",
    "        for i in range(n):\n",
    "            temp = dist[i]\n",
    "            temp.sort()\n",
    "            dict = {}\n",
    "            count = int(0)\n",
    "            \n",
    "            for j in range(n-1):\n",
    "                if temp[j+1] in dict :\n",
    "                    dict[temp[j+1]] = dict[temp[j+1]] + 1\n",
    "                else :\n",
    "                    dict[temp[j+1]] = 1\n",
    "           \n",
    "            for value in dict.values() :\n",
    "                if value<2 :\n",
    "                    continue\n",
    "                count += perm(value,2)\n",
    "            \n",
    "            total += count\n",
    "\n",
    "        return int(total)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        d = {}\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(points)):\n",
    "                distance = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2\n",
    "                if distance in d:\n",
    "                    d[distance].append(i)\n",
    "                else:\n",
    "                    d[distance] = [i]\n",
    "        d.pop(0)\n",
    "        ans = 0\n",
    "        for key in d:\n",
    "            dk = collections.Counter(d[key])\n",
    "            for tmpk, tmpv in dk.items():\n",
    "                ans += (tmpv - 1) * tmpv\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        graph = dict()\n",
    "        # initialize the graph\n",
    "        for i in range(len(points)):\n",
    "            graph[i] = list()\n",
    "\n",
    "        for index, point in enumerate(points):\n",
    "            start_x, start_y = point\n",
    "            for i in range(index, len(points)):\n",
    "                if i == index:\n",
    "                    continue\n",
    "                x, y = points[i]\n",
    "                dis = (x-start_x)**2+(y-start_y)**2\n",
    "                graph[index].append([i,dis])\n",
    "                graph[i].append([index, dis])\n",
    "        \n",
    "        ans = 0\n",
    "        def p(n,base = 2):\n",
    "            result = 1\n",
    "            for i in range(n, n-base,-1):\n",
    "                # print(i, result)\n",
    "                result *= i\n",
    "            return result\n",
    "\n",
    "        result_graph = list()\n",
    "        for index in graph.keys():\n",
    "            sort_dis = sorted(graph[index], key=lambda x:x[1])\n",
    "            if not sort_dis:\n",
    "                return 0\n",
    "            result_graph.append([])\n",
    "            same_dis_count = 1\n",
    "            pre_dis = sort_dis[0][1]\n",
    "            for j, dis in sort_dis[1:]:\n",
    "                if pre_dis == dis:\n",
    "                    same_dis_count += 1\n",
    "                else:\n",
    "                    pre_dis = dis\n",
    "                    result_graph[index].append(same_dis_count)\n",
    "                    if same_dis_count >= 2:\n",
    "                        ans += p(same_dis_count)\n",
    "                    same_dis_count = 1\n",
    "            if same_dis_count >= 2:\n",
    "                ans += p(same_dis_count)\n",
    "            result_graph[index].append(same_dis_count)\n",
    "        # print(result_graph, ans)\n",
    "        return ans\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from scipy.special import perm\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        return int(sum(sum(perm(num,2) \\\n",
    "        for dist,num in Counter([(point[0] - neighbor[0]) ** 2 \\\n",
    "        + (point[1] - neighbor[1]) ** 2 \\\n",
    "        for neighbor in points]).items() if num >= 2) \\\n",
    "        for point in points))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import defaultdict\n",
    "\n",
    "# class Solution:\n",
    "#     def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "#         res = 0\n",
    "#         d = defaultdict(dict)\n",
    "#         for i, (x1, y1) in enumerate(points):\n",
    "#             for j, (x2, y2) in enumerate(points[i + 1:], i + 1):\n",
    "#                 dis = (x1 - x2)**2 + (y1 - y2)**2\n",
    "#                 if dis in d[i]:\n",
    "#                     d[i][dis] += 1\n",
    "#                 else:\n",
    "#                     d[i][dis] = 1\n",
    "#                 if dis in d[j]:\n",
    "#                     d[j][dis] += 1\n",
    "#                 else:\n",
    "#                     d[j][dis] = 1\n",
    "#         for dd in d.values():\n",
    "#             for _, v in dd.items():\n",
    "#                 res += v * (v - 1)\n",
    "#         return int(res)\n",
    "\n",
    "\n",
    "# from collections import defaultdict\n",
    "\n",
    "# class Solution:\n",
    "#     def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "#         res = 0\n",
    "#         d = defaultdict(dict)\n",
    "#         for i, (x1, y1) in enumerate(points):\n",
    "#             for j, (x2, y2) in enumerate(points[i + 1:], i + 1):\n",
    "#                 dis = (x1 - x2)**2 + (y1 - y2)**2\n",
    "#                 if dis in d[i]:\n",
    "#                     d[i][dis] += 1\n",
    "#                 else:\n",
    "#                     d[i][dis] = 1\n",
    "#                 if dis in d[j]:\n",
    "#                     d[j][dis] += 1\n",
    "#                 else:\n",
    "#                     d[j][dis] = 1\n",
    "#             for _, v in d[i].items():\n",
    "#                 if v > 1:\n",
    "#                     res += v * (v - 1)\n",
    "#         return int(res)\n",
    "                \n",
    "\n",
    "# class Solution:\n",
    "#     def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "#         counter = 0\n",
    "#         for x1, y1 in points:\n",
    "#             cnt = {}\n",
    "#             for x2, y2 in points:\n",
    "#                 dis = (x1 - x2)**2 + (y1 - y2)**2\n",
    "#                 if dis in cnt:\n",
    "#                     counter += cnt[dis]\n",
    "#                     cnt[dis] += 1\n",
    "#                 else:\n",
    "#                     cnt[dis] = 1\n",
    "#         return counter * \n",
    "\n",
    "\n",
    "from scipy.spatial.distance import cdist\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        mat = cdist(points, points)\n",
    "        res = 0\n",
    "        for line in mat:\n",
    "            d = {}\n",
    "            for x in line:\n",
    "                if x not in d:\n",
    "                    d[x] = 1\n",
    "                else:\n",
    "                    res += d[x]\n",
    "                    d[x] += 1\n",
    "        return res * 2\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        graph = dict()\n",
    "        # initialize the graph\n",
    "        for i in range(len(points)):\n",
    "            graph[i] = list()\n",
    "\n",
    "        for index, point in enumerate(points):\n",
    "            start_x, start_y = point\n",
    "            for i in range(index, len(points)):\n",
    "                if i == index:\n",
    "                    continue\n",
    "                x, y = points[i]\n",
    "                dis = (x-start_x)**2+(y-start_y)**2\n",
    "                graph[index].append([i,dis])\n",
    "                graph[i].append([index, dis])\n",
    "        \n",
    "        ans = 0\n",
    "        def p(n,base = 2):\n",
    "            result = 1\n",
    "            for i in range(n, n-base,-1):\n",
    "                # print(i, result)\n",
    "                result *= i\n",
    "            return result\n",
    "\n",
    "        result_graph = list()\n",
    "        for index in graph.keys():\n",
    "            sort_dis = sorted(graph[index], key=lambda x:x[1])\n",
    "            if not sort_dis:\n",
    "                return 0\n",
    "            result_graph.append([])\n",
    "            same_dis_count = 1\n",
    "            pre_dis = sort_dis[0][1]\n",
    "            for j, dis in sort_dis[1:]:\n",
    "                if pre_dis == dis:\n",
    "                    same_dis_count += 1\n",
    "                else:\n",
    "                    pre_dis = dis\n",
    "                    result_graph[index].append(same_dis_count)\n",
    "                    if same_dis_count >= 2:\n",
    "                        ans += p(same_dis_count)\n",
    "                    same_dis_count = 1\n",
    "            if same_dis_count >= 2:\n",
    "                ans += p(same_dis_count)\n",
    "            result_graph[index].append(same_dis_count)\n",
    "        print(result_graph, ans)\n",
    "        return ans\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        distance_dict = collections.defaultdict(list)\n",
    "        for i in range(len(points)):\n",
    "            start = i + 1\n",
    "            for j in range(start, len(points)):\n",
    "                dis = (points[i][0] - points[j][0]) **2 + (points[i][1] - points[j][1]) ** 2\n",
    "                distance_dict[dis].append((points[i], points[j]))\n",
    "        for key, val in distance_dict.items():\n",
    "            if len(val) <= 1:\n",
    "                continue\n",
    "            all_points = [(x[0], x[1]) for ele in val for x in ele]\n",
    "            points_times = dict(collections.Counter(all_points))\n",
    "            for points, times in points_times.items():\n",
    "                if times <= 1:\n",
    "                    continue\n",
    "                ans += times * (times -1)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dist(p1, p2):\n",
    "            return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2\n",
    "        N = len(points)\n",
    "        ds = {}\n",
    "        for i in range(N):\n",
    "            p1 = tuple(points[i])\n",
    "            d = defaultdict(int)\n",
    "            for j in range(N):\n",
    "                if i == j: continue\n",
    "                p2 = tuple(points[j])\n",
    "                d[dist(min(p1, p2), max(p1, p2))] += 1\n",
    "            ds[p1] = d\n",
    "        cnt = 0\n",
    "        for _, d in ds.items():\n",
    "            for v, n in d.items():\n",
    "                cnt += n * (n-1)\n",
    "        return cnt\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        dis_dict = collections.defaultdict(list)\n",
    "        size = len(points)\n",
    "        if size < 3:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(1, size):\n",
    "            for j in range(0, i):\n",
    "                points_dis = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2\n",
    "                pos = (i, j)\n",
    "                dis_dict[points_dis].append(pos)\n",
    "        \n",
    "        counter = 0\n",
    "        for key in dis_dict.keys():\n",
    "            com_dis_size = len(dis_dict[key])\n",
    "            if com_dis_size >= 2:\n",
    "                for i in range(1, com_dis_size):\n",
    "                    for j in range(0, i):\n",
    "                        i_set = set(dis_dict[key][i])\n",
    "                        j_set = set(dis_dict[key][j])\n",
    "                        union_p = i_set | j_set\n",
    "                        \n",
    "                        if len(union_p) == 3:\n",
    "                            counter += 2\n",
    "\n",
    "        return counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from unittest import result\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        result_sum=0\n",
    "        distance_dict={}\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1,len(points)):\n",
    "                distance=(points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2\n",
    "                if distance not in distance_dict:\n",
    "                    distance_dict[distance]=[[points[i]]+[points[j]]]\n",
    "                else:\n",
    "                    if [points[i],points[j]] not in distance_dict[distance] and \\\n",
    "                    [points[j],points[i]] not in distance_dict[distance]:\n",
    "                        distance_dict[distance]=distance_dict[distance]+[[points[i]]+[points[j]]]\n",
    "        #print(distance_dict)\n",
    "        for k,v in distance_dict.items():\n",
    "            temp_cnt_dict={}\n",
    "            for vv in v:\n",
    "                for vvv in vv:\n",
    "                    if str(vvv) in temp_cnt_dict:\n",
    "                        temp_cnt_dict[str(vvv)]=temp_cnt_dict[str(vvv)]+1\n",
    "                    else:\n",
    "                        temp_cnt_dict[str(vvv)]=1 \n",
    "            #print(temp_cnt_dict)\n",
    "            for k2,v2 in temp_cnt_dict.items():\n",
    "                if v2>=2:\n",
    "                    result_sum+=v2*(v2-1)\n",
    "        return result_sum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n=len(points)\n",
    "        d=defaultdict(dict)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                dis=(points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2\n",
    "                d[i][dis]=d[i].get(dis,[])+[j]\n",
    "                d[j][dis]=d[j].get(dis,[])+[i]\n",
    "        res=0\n",
    "        for j in d.keys():\n",
    "            for dis in d[j]:\n",
    "                for i in d[j][dis]:\n",
    "                    for k in d[j][dis]:\n",
    "                        if len({i,j,k})==3:\n",
    "                            res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        point_distance = defaultdict(dict)\n",
    "        if len(points) < 3:\n",
    "            return 0\n",
    "        else:\n",
    "            length = len(points)\n",
    "            for i in range(length):\n",
    "                for j in range(i + 1, length):\n",
    "                    dis = pow(points[i][1] - points[j][1], 2) + pow(points[i][0] - points[j][0], 2)\n",
    "                    if dis not in point_distance[i]:\n",
    "                        point_distance[i][dis] = [j]\n",
    "                    else:\n",
    "                        point_distance[i][dis].append(j)\n",
    "                    if dis not in point_distance[j]:\n",
    "                        point_distance[j][dis] = [i]\n",
    "                    else:\n",
    "                        point_distance[j][dis].append(i)\n",
    "            result = 0\n",
    "            for key, value in point_distance.items():\n",
    "                for dis, index_list in value.items():\n",
    "                    length = len(index_list)\n",
    "                    if length < 2:\n",
    "                        continue\n",
    "                    else:\n",
    "                        result += length * (length - 1)\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        point_distance = defaultdict(dict)\n",
    "        if len(points) < 3:\n",
    "            return 0\n",
    "        else:\n",
    "            length = len(points)\n",
    "            for i in range(length):\n",
    "                for j in range(i + 1, length):\n",
    "                    dis = pow(points[i][1] - points[j][1], 2) + pow(points[i][0] - points[j][0], 2)\n",
    "                    if dis not in point_distance[i]:\n",
    "                        point_distance[i][dis] = [j]\n",
    "                    else:\n",
    "                        point_distance[i][dis].append(j)\n",
    "                    if dis not in point_distance[j]:\n",
    "                        point_distance[j][dis] = [i]\n",
    "                    else:\n",
    "                        point_distance[j][dis].append(i)\n",
    "            result = 0\n",
    "            for key, value in point_distance.items():\n",
    "                for dis, index_list in value.items():\n",
    "                    length = len(index_list)\n",
    "                    if length < 2:\n",
    "                        continue\n",
    "                    else:\n",
    "                        result += length * (length - 1)\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "def calc(a, b):\n",
    "    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        m = defaultdict(list)\n",
    "        n = len(points)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                pi, pj = points[i], points[j]\n",
    "                tar = calc(pi, pj)\n",
    "\n",
    "                for ppi, ppj in m[tar]:\n",
    "                    if ppi == i or ppi == j:\n",
    "                        res += 1\n",
    "                    if ppj == i or ppj == j:\n",
    "                        res += 1\n",
    "\n",
    "                m[tar].append((i, j))\n",
    "\n",
    "\n",
    "        return res * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        table = {}\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                dist = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2 \n",
    "                if not dist in table:\n",
    "                    table[dist] = []\n",
    "                table[dist].append([i,j])\n",
    "        \n",
    "        ans = 0\n",
    "        for key in table:\n",
    "            pairs = table[key]\n",
    "            # print(\"key = \", key, \" len = \", len(pairs))\n",
    "            for i in range(len(pairs)):\n",
    "                for j in range(i+1, len(pairs)):\n",
    "                    if pairs[i][0] in pairs[j] or pairs[i][1] in pairs[j]:\n",
    "                        ans += 2\n",
    "\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        d = {}\n",
    "        def jisuan(i,j):\n",
    "            a = pow(i[0]-j[0],2)\n",
    "            b = pow(i[1]-j[1],2)\n",
    "            return a+b\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1,len(points)):\n",
    "                x = jisuan(points[i],points[j])\n",
    "                if x not in d:\n",
    "                    d[x] = []\n",
    "                d[x].append([i,j])\n",
    "        r = 0\n",
    "        def jicheng(n):\n",
    "            return n*(n-1)\n",
    "        for i in d:\n",
    "            temp = {}\n",
    "            for j in d[i]:\n",
    "                if j[0] not in temp:\n",
    "                    temp[j[0]] = []\n",
    "                temp[j[0]].append(j[1])\n",
    "                if j[1] not in temp:\n",
    "                    temp[j[1]] = []\n",
    "                temp[j[1]].append(j[0])\n",
    "            for j in temp:\n",
    "                if len(temp[j]) > 1:\n",
    "                    r += jicheng(len(temp[j]))\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        dis=defaultdict(lambda : defaultdict(list))\n",
    "        calc=lambda x,y:sqrt((x[0]-y[0])**2+(x[1]-y[1])**2)\n",
    "        for i,x in enumerate(points):\n",
    "            for j,y in enumerate(points[i+1:]):\n",
    "                j=j+i+1\n",
    "                val=calc(x,y)\n",
    "                dis[i][val].append(j)\n",
    "                dis[j][val].append(i)\n",
    "        res=set()\n",
    "        for i,d in dis.items():\n",
    "            for _,js in d.items():\n",
    "                for idx,j1 in enumerate(js):\n",
    "                    for j2 in js[idx+1:]:\n",
    "                        res.add((i,j1,j2))\n",
    "                        res.add((i,j2,j1))\n",
    "        return len(res)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        n = len(points)\n",
    "        mp = defaultdict(int) \n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                dis = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2 \n",
    "                res += mp[(i,dis)] + mp[(j,dis)]\n",
    "                mp[(i,dis)] += 1\n",
    "                mp[(j,dis)] += 1 \n",
    "        return res << 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        dist_dict = dict()\n",
    "        n = len(points)\n",
    "        for i in range(n):\n",
    "            point1 = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                point2 = points[j]\n",
    "                dist = (point1[0]-point2[0]) ** 2 + (point1[1]-point2[1]) ** 2\n",
    "                dist_dict[(point1[0], point1[1], dist)] = dist_dict.get((point1[0], point1[1], dist), 0) + 1\n",
    "                dist_dict[(point2[0], point2[1], dist)] = dist_dict.get((point2[0], point2[1], dist), 0) + 1\n",
    "        ans = 0\n",
    "        for dist, cnt in dist_dict.items():\n",
    "            if cnt >= 2:\n",
    "                ans += cnt * (cnt-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        points = [tuple(i) for i in points]\n",
    "        rec = {}\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i + 1, len(points)):\n",
    "                x,y = points[i], points[j]\n",
    "                s = (x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2\n",
    "                if s not in rec:\n",
    "                    rec[s] = {x : 1, y : 1}\n",
    "                else:\n",
    "                    if x not in rec[s]:\n",
    "                        rec[s][x] = 1\n",
    "                    else:\n",
    "                        rec[s][x] += 1\n",
    "                    if y not in rec[s]:\n",
    "                        rec[s][y] = 1\n",
    "                    else:\n",
    "                        rec[s][y] += 1\n",
    "        return sum([sum([g * (g - 1) for g in i.values() if g >= 2]) for i in rec.values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        dis = collections.defaultdict(int) \n",
    "\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1, len(points)):\n",
    "                d = (points[j][0]-points[i][0])**2 + (points[j][1]-points[i][1])**2\n",
    "\n",
    "                dis[(i,d)] += 1\n",
    "                dis[(j,d)] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for key in dis.keys():\n",
    "            ans += dis[key]*(dis[key]-1)\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        tracker = defaultdict(lambda: 0)\n",
    "        for i, [x, y] in enumerate(points):\n",
    "            for j, [a, b] in enumerate(points[i+1:], start=i+1):\n",
    "                dist = (x-a)**2 + (y-b)**2\n",
    "                tracker[(i, dist)] += 1\n",
    "                tracker[(j, dist)] += 1\n",
    "        \n",
    "        return sum(count * (count-1) for count in tracker.values() if count >= 2)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        distMap = {}\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                x,y = points[i],points[j]\n",
    "                area = (x[0]-y[0])**2 + (x[1]-y[1])**2\n",
    "                distMap[(i,area)] = distMap.get((i,area),0)+1\n",
    "                distMap[(j,area)] = distMap.get((j,area),0)+1\n",
    "        cnt = 0\n",
    "        for key,val in distMap.items():\n",
    "            if val >= 2:\n",
    "                cnt += (val*(val-1))\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, p: List[List[int]]) -> int:\n",
    "        dis = defaultdict(int)\n",
    "        ans = 0\n",
    "        n = len(p)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                d = dist(p[i], p[j])\n",
    "                dis[(d, i)] += 1\n",
    "                dis[(d, j)] += 1\n",
    "        for v in dis.values():\n",
    "            if v >= 2:\n",
    "                ans += v * (v - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        length = len(points)\n",
    "        if length < 3:\n",
    "            return 0\n",
    "        output = 0\n",
    "        dist = {}\n",
    "        for i in range(length):\n",
    "            for j in range(length):\n",
    "                if i != j:\n",
    "                    temp = (points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2\n",
    "                    tempList = dist.get(temp, [])\n",
    "                    tempList.append((i,j))\n",
    "                    dist[temp] = tempList\n",
    "        for key in dist:\n",
    "            if len(dist[key]) < 3:\n",
    "                continue\n",
    "            else:\n",
    "                for point1 in dist[key]:\n",
    "                    for point2 in dist[key]:\n",
    "                        if point1 != point2:\n",
    "                            if point1[0] == point2[0] and point1[1] != point2[1]:\n",
    "                                output += 1\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        d = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if (points[i] != points[j]):\n",
    "                    ij = (points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2\n",
    "                    d[ij].append([points[i], points[j]])\n",
    "        res = []\n",
    "        for groups in d.values():\n",
    "            d2 = defaultdict(list)\n",
    "            for pairs in groups:\n",
    "                k = tuple(pairs[0])\n",
    "                d2[k].append(pairs)\n",
    "            res += [p for p in d2.values() if len(p)>=2]\n",
    "        ans = 0\n",
    "        for r in res:\n",
    "            cnt = len(r)\n",
    "            ans += cnt*(cnt-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        dt=dict()\n",
    "        dt=defaultdict(dict)\n",
    "        l=len(points)\n",
    "        if l<3:\n",
    "            return 0\n",
    "        for i in range(l-1):\n",
    "            for j in range(i+1,l):\n",
    "                ax,ay,bx,by=points[i][0],points[i][1],points[j][0],points[j][1]\n",
    "                dis=(ax-bx)**2+(ay-by)**2\n",
    "                #return dis,dt[dis]\n",
    "                d=dt[dis]\n",
    "                if i in d.keys():                                    \n",
    "                    dt[dis][i]+=1                    \n",
    "                else:\n",
    "                    dt[dis][i]=1\n",
    "                if j in d.keys():                                    \n",
    "                    dt[dis][j]+=1                    \n",
    "                else:\n",
    "                    dt[dis][j]=1\n",
    "                    \n",
    "                \n",
    "        ans=0\n",
    "        #return dt\n",
    "        for a in dt.values():\n",
    "            ans+=sum(b*(b-1) for b in a.values())\n",
    "        return ans            \n",
    "                                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "def calc(a, b):\n",
    "    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        m = defaultdict(list)\n",
    "        n = len(points)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                pi, pj = points[i], points[j]\n",
    "                m[calc(pi, pj)].append((i, j))\n",
    "        # print(m)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if i == j: continue\n",
    "                pi, pj = points[i], points[j]\n",
    "\n",
    "                for ppi, ppj in m[calc(pi, pj)]:\n",
    "                    if (ppi == i and ppj != j) or (ppi == j and ppj != i):\n",
    "                        res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points) :\n",
    "        nums=points\n",
    "        l_nums = len(nums)\n",
    "        ret = []\n",
    "        for i in range(l_nums - 1):\n",
    "            for j in range(i + 1, l_nums):\n",
    "                a = []\n",
    "                distance =pow ((nums[i][0] - nums[j][0]),2) + pow((nums[i][1] - nums[j][1]),2)\n",
    "                a.append(distance)\n",
    "                a.append([i, j])\n",
    "                ret.append(a)\n",
    "        count = 0\n",
    "        a = {}\n",
    "        ll=len(ret)\n",
    "        for i in range(ll):\n",
    "            if ret[i][0] not in a.keys():\n",
    "                a[ret[i][0]] = [ret[i][1]]\n",
    "            else:\n",
    "                for x in a[ret[i][0]]:\n",
    "                    if x[0]==ret[i][1][0] or  x[1] == ret[i][1][0]:\n",
    "                        count += 2\n",
    "                    if ret[i][1][1]==x[1]:\n",
    "                        count += 2\n",
    "                a[ret[i][0]].append(ret[i][1])\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dis(i, j):\n",
    "            if i > j:\n",
    "                i, j = j, i\n",
    "            return (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2\n",
    "        ret = 0\n",
    "        for i in range(len(points)):\n",
    "            d = defaultdict(int)\n",
    "            for j in range(len(points)):\n",
    "                d[dis(i, j)] += 1\n",
    "            for v in d.values():\n",
    "                if v > 1:\n",
    "                    ret += v * (v-1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        distances = {}\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i+1, len(points)):\n",
    "                count = 0\n",
    "                first, second = points[i], points[j]\n",
    "                d = (first[0]-second[0])**2+(first[1]-second[1])**2\n",
    "                if d in distances:\n",
    "                    if i in distances[d]: count += distances[d][i]\n",
    "                    if j in distances[d]: count += distances[d][j]\n",
    "                if d not in distances:\n",
    "                    distances[d] = defaultdict(int)\n",
    "                distances[d][i] += 1\n",
    "                distances[d][j] += 1\n",
    "                res += count\n",
    "        return res*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfBoomerangs(self, points: List[List[int]]) -> int:\n",
    "        dismap = {}\n",
    "        n = len(points)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                dis = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2\n",
    "                if dis not in dismap:\n",
    "                    dismap[dis] = collections.defaultdict(int)\n",
    "                dismap[dis][i] += 1\n",
    "                dismap[dis][j] += 1\n",
    "        ans = 0\n",
    "        for v in dismap.values():\n",
    "            for vv in v.values():\n",
    "                ans += vv*(vv-1)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
